package com.jxb.seven;

import java.util.Arrays;

/**
 * 零钱兑换???
 *
 * 输入：coins = [1, 2, 5], amount = 11
 * 输出：3
 *
 * @author jiaobo
 * @date Created in 2025/1/5 19:45
 **/
public class CoinChange_322 {

    //dp[i][j]：从i种硬币种选，选出总金额j的最小硬币数
    //m:i-1位置的面值，k是需要种硬币
    //dp[i][j] = min(dp[i-1][j],dp[i-1][j-m]+1,dp[i-1][j-2*m] + 2,...,dp[i-1][j-k*m] + k)
    //eg:coins = [3, 2, 5], amount = 7，m = coins[i-1]
    //前2种硬币中选：min(dp[2-1][5],dp[2][5-2] + 1) = 1
    //前3种硬币中选：min(dp[3-1][7],dp[3][7-5] + 1) = 2
    //j-m = 2
    //dp[2-1][5-2] =
    public int coinChangeAll(int[] coins, int amount) {
        int n = coins.length;
        int impossible = amount + 1;
        //定义dp数组，行是元数组长度加一，列是总金额加一
        int[][] dp = new int[n+1][impossible];
        //初始化dp数组-将所有元素填充为总金额+1,(0,0)元素置为0
        for (int i = 0;i<=n;i++) {
            for (int j = 0;j<=amount;j++) {
                dp[i][j] = impossible;
            }
        }
        dp[0][0] = 0;
        //dp数组填充
        for (int i = 1;i<=n;i++) {
            //第i个面值的前一个
            int m = coins[i-1];
            for (int j = 0;j<=amount;j++) {
                //遍历比j小的需要多少种硬币
                for (int k = 0;k*m <= j; k++) {
                    //dp[i-1][j-k*m]表示需要k个i-1位置的面值，然后总个数就等于dp[i-1][j-k*m] + k
                    dp[i][j] = Math.min(dp[i][j],dp[i-1][j-k*m] + k);
                }
            }
        }

        return dp[n][amount] == impossible ? -1:dp[n][amount];

    }

    /*第二版实现*/
    public int coinChange(int[] coins, int amount) {
        int impossible  = amount+1;
        int[] dp = new int[impossible];
        /*初始化dp数组，每个元素最多的硬币个数一定是i值本身，
        通过判断DP数组最后一个值是否为amount+1返回最终结果*/
        Arrays.fill(dp, impossible);
        dp[0] = 0;
        /*对于dp数组中的每个元素，判断当前元素（金额）如何由coins组成可以个数最少
         * 对于每个金额i都会遍历coins数组一次计算个数，并填充dp数组*/
        //滚动数组
        int n = coins.length;
        for (int i = 0;i<n;i++) {
            for (int j = 1;j<=amount;j++) {
                if (j>=coins[i]) {
                    dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }
        return dp[amount] == impossible ? -1:dp[amount];
    }

}
